package com.xsherl.leetcode.solution;

import cn.hutool.core.lang.Assert;
import com.xsherl.leetcode.utils.ArrayUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: sherl
 * @Date: 2021/5/24 21:04
 */
public class LetterCombinations {

    private char[][] chars = new char[][]{
            {},
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'}
    };

    /**
     *
     * @param digits
     * 0 <= digits.length <= 4
     * digits[i] 是范围 ['2', '9'] 的一个数字。
     */
    public List<String> letterCombinations(String digits) {
        int len = digits.length();
        if (len == 0) {
            return new ArrayList<>();
        }
        int size = 1;
        char[] toCharArray = digits.toCharArray();
        // 计算一共有多少种组合方式
        for (char d : toCharArray) {
            char[] aChar = this.chars[d - '1'];
            size *= aChar.length;
        }
        // 初始化组合
        List<char[]> charList = new ArrayList<>(size);
        for (int k = 0; k < size; ++k) {
            char[] charArr = new char[len];
            charList.add(charArr);
        }
        int step = size;
        // 根据步进写入字符，步进与所属按键长度有关
        for (int x = 0; x < toCharArray.length; ++x) {
            char[] aChar = this.chars[toCharArray[x] - '1'];
            step /= aChar.length;
            int m = -1;
            for (int y = 0; y < size; y++) {
                if (y % step == 0) {
                    m++;
                    if (m >= aChar.length) {
                        m = m % aChar.length;
                    }
                }
                char[] charArr = charList.get(y);
                charArr[x] = aChar[m];
            }
        }

        List<String> res = new ArrayList<>(size);
        for (char[] cr : charList) {
            res.add(String.valueOf(cr));
        }
        return res;
    }

    public static void main(String[] args) {
        String digits = "23";
        List<String> strings = new LetterCombinations().letterCombinations(digits);
        System.out.println(strings);
        String[] strings1 = ArrayUtils.parseArray("[\"ad\",\"ae\",\"af\",\"bd\",\"be\",\"bf\",\"cd\",\"ce\",\"cf\"]", String.class);
        Assert.isTrue(Arrays.equals(strings.toArray(new String[0]), strings1));
    }

}
